package ACM.HuaWei;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author way
 * @create 2025-04-09 22:25
 */
public class _2 {
    static class Edge {
        char target;
        int time;

        Edge(char target, int time) {
            this.target = target;
            this.time = time;
        }
    }

    static class Node {
        char vertex;
        int distance;

        Node(char vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.nextLine();
        String[] startEnd = scanner.nextLine().split(" ");
        char startNode = startEnd[0].charAt(0);
        char endNode = startEnd[1].charAt(0);

        Map<Character, List<Edge>> adjacencyMap = new HashMap<>();

        while (scanner.hasNextLine()) {
            String inputLine = scanner.nextLine();
            if (inputLine.equals("0000")) {
                break;
            }

            String[] parts = inputLine.split("\\s+");
            if (parts.length != 3) continue;

            char fromNode = parts[0].charAt(0);
            char toNode = parts[1].charAt(0);
            int time;
            try {
                time = Integer.parseInt(parts[2]);
            } catch (NumberFormatException e) {
                continue;
            }

            adjacencyMap.putIfAbsent(fromNode, new ArrayList<>());
            adjacencyMap.get(fromNode).add(new Edge(toNode, time));
            adjacencyMap.putIfAbsent(toNode, new ArrayList<>());
            adjacencyMap.get(toNode).add(new Edge(fromNode, time));
        }

        Map<Character, Integer> distanceMap = new HashMap<>();
        Map<Character, Character> predecessorMap = new HashMap<>();
        PriorityQueue<Node> minHeap = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));

        for (Character node : adjacencyMap.keySet()) {
            distanceMap.put(node, Integer.MAX_VALUE);
        }
        distanceMap.put(startNode, 0);
        minHeap.offer(new Node(startNode, 0));

        while (!minHeap.isEmpty()) {
            Node current = minHeap.poll();
            char currentNode = current.vertex;
            int currentDistance = current.distance;

            if (currentDistance > distanceMap.get(currentNode)) continue;

            for (Edge edge : adjacencyMap.getOrDefault(currentNode, Collections.emptyList())) {
                char neighborNode = edge.target;
                int newDistance = currentDistance + edge.time;
                if (newDistance < distanceMap.getOrDefault(neighborNode, Integer.MAX_VALUE)) {
                    distanceMap.put(neighborNode, newDistance);
                    predecessorMap.put(neighborNode, currentNode);
                    minHeap.offer(new Node(neighborNode, newDistance));
                }
            }
        }

        List<Character> path = new ArrayList<>();
        char current = endNode;
        while (current != startNode) {
            path.add(current);
            Character prevNode = predecessorMap.get(current);
            if (prevNode == null) break;
            current = prevNode;
        }
        path.add(startNode);
        Collections.reverse(path);

        System.out.println(path.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}
